package fast_slow_pointer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 剑指 Offer II 026. 重排链表 https://leetcode.cn/problems/LGjMqU/
 * @Author Firenut
 * @Date 2023-02-15 17:42
 */
public class T026_reorderList {
    @Test
    public void test() {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = null;
//        ListNode node = formatList2(n1);
//        while (node != null) {
//            System.out.print(node.val+" ");
//            node = node.next;
//        }
    }



    // 法2 : 快慢指针找中点，反转链表后半部分，合并前后两个链表
    // 时间复杂度: O(n): 求中点的时间复杂度为O(N); 反转链表的时间复杂度同为O(n); 合并链表的时间复杂度同为O(n)
    // 空间复杂度:O(1): 没有用到额外的空间
    public void reorderList(ListNode head) {
        ListNode mid = midNode(head); // 返回中间结点
        ListNode afterList= mid.next;
        mid.next=null;       //断开前后两部分链表
        if(afterList==null){ //afterList可能为null,比如head = [1]
            return;
        }
        ListNode after = reverse(afterList);// 后半部分链表的头结点
        merge(head,after);
    }

    // 返回链表的中间节点(快慢指针找中点)
    ListNode midNode(ListNode head){
        ListNode fast, slow;
        fast = slow = head;
        while (fast != null && fast.next != null) { //写 while(fast.next!=null&&fast.next.next!=null) 也可以
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    // 反转链表(此时后半部分的链表已经断开和前半部分的连接,但是前半部分的next仍指向后半部分,也即next没有断开)
    ListNode reverse(ListNode head) {
        ListNode pre, cur, next;
        pre = null;
        cur = head;

        next = cur.next;

        while (next != null) {
            cur.next = pre;
            pre = cur;
            cur = next;
            next = next.next;
        }
        cur.next = pre;
        return cur;
    }

    // 合并两个链表(使用四个指针；也可以使用递归，但是需要多传入一个boolean变量)
    void merge(ListNode l1, ListNode l2) {
        ListNode p1, p2;
        p1 = l1;
        p2 = l2;
        while (p1 != null && p2 != null) {
            ListNode p11 = p1.next;
            ListNode p22 = p2.next;
            p1.next = p2;
            p2.next = p11;
            p1 = p11;
            p2 = p22;
        }
    }

    // 合并两个链表(递归解法)
    ListNode merge(ListNode l1,ListNode l2,boolean flag){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        if(flag){
            l1.next = merge(l1.next, l2, false);
            return l1;
        }else{
            l2.next = merge(l1, l2.next, true);
            return l2;
        }
    }


    // ---------------------------
    // 法1:双指针+线性表
//    时间复杂度: O(n):
//    空间复杂度:O(n)
    public void reorderList1(ListNode head) {
        List<ListNode> list = new ArrayList<>(); //list有序表维护的是链表未反转前的先后顺序
        ListNode p=head;
        while(p!=null){
            list.add(p);
            p=p.next;
        }

        int i=0,j=list.size()-1;
        while(i<j){
            list.get(i).next=list.get(j);
            i++;
            if(i>=j){
                break;
            }
            list.get(j).next=list.get(i);
            j--;
        }
        list.get(i).next=null;
    }
}
